package main

import (
	"fmt"
	"github.com/Workiva/go-datastructures/queue"
	"math"
)

type Node struct {
	key int
	value int
	left *Node
	right *Node
}

func newNode(key int, value int) *Node{
	n := new(Node)
	n.key = key
	n.value = value
	n.left = nil
	n.right = nil
	return n
}

type BST struct {
	root *Node
	count int
}

func (bst *BST) Size() int {
	return bst.count
}

func (bst *BST) IsEmpty() bool {
	return bst.count == 0
}

func (bst *BST) Insert(key int, value int) {
	bst.root = bst.insert(bst.root, key, value)
}

func (bst *BST) insert(node *Node, key int, value int) *Node {

	if node == nil {
		bst.count++
		return newNode(key, value)
	}

	if key == node.key {
		node.value = value
	} else if key < node.key {
		node.left = bst.insert(node.left, key, value)
	} else {
		node.right = bst.insert(node.right, key, value)
	}

	return node
}

func (bst *BST) contain(node *Node, target int) bool {

	if node == nil {
		return false
	}

	if node.key == target {
		return true
	} else if target < node.key {
		return bst.contain(node.left, target)
	} else {
		return bst.contain(node.right, target)
	}
}

func (bst *BST) search(node *Node, target int) *int {

	if node == nil {
		return nil
	}

	if node.key == target {
		return &node.value
	} else if target < node.key {
		return bst.search(node.left, target)
	} else {
		return bst.search(node.right, target)
	}
}

// 前序遍历
func (bst *BST) PreOrder() {
	bst.preOrder(bst.root)
}

func (bst *BST) preOrder(node *Node) {
	if node != nil {
		println(node.key)
		bst.preOrder(node.left)
		bst.preOrder(node.right)
	}
}

// 中序遍历 从小到大
func (bst *BST) InOrder() {
	bst.inOrder(bst.root)
}

func (bst *BST) inOrder(node *Node) {
	if node != nil {
		bst.inOrder(node.left)
		println(node.key)
		bst.inOrder(node.right)
	}
}

// 后序遍历 先释放左右两个子树，可用户释放整个树的时候使用
func (bst *BST) PostOrder() {
	bst.postOrder(bst.root)
}

func (bst *BST) postOrder(node *Node) {
	if node != nil {
		bst.postOrder(node.left)
		bst.postOrder(node.right)
		println(node.key)
	}
}

// 层序遍历
func (bst *BST) LevelOrder() {
	bst.levelOrder(bst.root)
}

func (bst *BST) levelOrder(node *Node) {

	queue := queue.New(int64(bst.Size()))
	queue.Put(node)

	for !queue.Empty() {
		items, _ := queue.Get(1)
		first := items[0].(*Node)

		fmt.Println(first.value)

		if first.left != nil {
			queue.Put(first.left)
		}
		if first.right != nil {
			queue.Put(first.right)
		}

	}
}

func (bst *BST) Min() *Node {
	return bst.min(bst.root)
}

func (bst *BST) min(node *Node) *Node {
	if node.left != nil {
		return bst.min(node.left)
	}

	return node
}

func (bst *BST) Max() *Node {
	return bst.max(bst.root)
}

func (bst *BST) max(node *Node) *Node {
	if node.right != nil {
		return bst.max(node.right)
	}

	return node
}

func (bst *BST) RemoveMin() {
	if bst.root != nil {
		bst.root = bst.removeMin(bst.root)
	}
}

func (bst *BST) removeMin(node *Node) *Node {
	if node.left == nil {
		rightNode := node.right
		bst.count--
		return rightNode
	}

	node.left = bst.removeMin(node.left)
	return node
}

func (bst *BST) RemoveMax() {
	if bst.root != nil {
		bst.root = bst.removeMax(bst.root)
	}
}

func (bst *BST) removeMax(node *Node) *Node {
	if node.right == nil {
		leftNode := node.left
		bst.count--
		return leftNode
	}

	node.right = bst.removeMax(node.right)
	return node
}

func (bst *BST) Remove(key int) {
	bst.root = bst.remove(bst.root, key)
}

func (bst *BST) remove(node *Node, key int) *Node {
	if node == nil {
		return nil
	}

	if key < node.key {
		node.left = bst.remove(node.left, key)
		return node
	} else if key > node.key {
		node.right = bst.remove(node.right, key)
		return node
	} else {
		if node.left == nil {
			rightNode := node.right
			bst.count--
			return rightNode
		}

		if node.right == nil {
			leftNode := node.left
			bst.count--
			return leftNode
		}

		// 后继者
		min := bst.min(node.right)
		successor := newNode(min.key, min.value)
		successor.left = node.left
		successor.right = bst.removeMin(node.right)
		bst.count--
		return successor
	}

}

// 树高
func (bst *BST) Level() int {
	return bst.level(bst.root)
}

func (bst *BST) level(node *Node) int {

	if node == nil {
		return 0
	}

	return int(math.Max(float64(bst.level(node.left)), float64(bst.level(node.right)))) + 1
}

func (bst *BST) Delete() {
	//bst.root = nil
	bst.delete(bst.root)
}

func (bst *BST) delete(node *Node) {
	node = nil
	//if node != nil {
	//	bst.delete(node.left)
	//	bst.delete(node.right)
	//	fmt.Println(node)
	//	bst.count--
	//}
}








